COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	4.0	A POLYHEDRON INTERSECTION ALGORITHM.
C00003 00003	FIXUP1
C00006 ENDMK
C⊗;
4.0	A POLYHEDRON INTERSECTION ALGORITHM.

4.0	Introduction to Polyhedron Intersection.
4.1	Algorithm.
4.2	Performance.

4.0	Introduction to Polyhedron Intersection.

4.1	Algorithm.

	The polyhderon intersection algorithm consists  of two parts: first
there  is a  geometric  part in  which all  the  faces and  edges are
compared  for  potential   intersections  and   second  there  is   a
topological part in which the desired result polyhedron is copied off of
the given polyhedra.

MKSURF
OTHERV
ETRACE

COMMENT	FIXUP1

	FIXUP1 places vertex and wing pointers in all the non-surface
edges. A non-surface  edge is distinguished by its non-zero ALT link,
and the new vertices are provided with a A as a first edge,  PED, if
it be lacking.;

	A←BODY0;
WHILE (A←PED(A)) ≠ BODY0 DO IF (E←ALT(A))≠0 THEN
BEGIN
	PVT(A)	←V←	ALT(PVT(E)); IF PED(V)=0 THEN PED(V)←A;
	NVT(A)	←V←	ALT(NVT(E)); IF PED(V)=0 THEN PED(V)←A;
	NCW(A)	←	ALT(NCW(E));
	PCW(A)	←	ALT(PCW(E));
	NCCW(A)	←	ALT(NCCW(E));
	PCCW(A)	←	ALT(PCCW(E));
END;

COMMENT FIXUP2

	FIXUP2 wigns together  the surface vertex  tridedral corners.
Since it  is our good luck that  all surface vertices are necessarily
trihedral, the edges can be passed to the WING primitive for oriented
linking, in  any order.   The two surface  wings of a  surface vertex
were  stored in the NED and PED links  by MKSURF; the inward wing can
be retrieve as the PED(ALT(U)). Surface vertices are distinguished by
their ALT vertex having his SURBIT on.;

COMMENT FIXUP3

	FIXUP3  replaces the  alein  faces of  the  result body  with
native  faces; this  is done by  scaning the  edge ring of  the body,
testing the  two faces of  each edge  to see  if they  belong to  the
result body,  and if a  face doesn't belong it  is replaced by  a new
one.  Face replacement,  as ususal,  requires clocking around  a face
perimeter and changing the appropriate face link in each edge.